package cn.cnsuh.剑指offer.q39_数组中出现次数超过一半的数字;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 1, 12, 2, 3, 3, 3};
        System.out.println("fun1(arr) = " + fun1(arr));
        System.out.println("fun2(arr) = " + fun2(arr));

    }

    static int fun1(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2 - 1];
    }

    static int fun2(int[] nums) {
        int ans = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) ans = num;
            votes += num == ans ? 1 : -1;
        }
        return ans;
    }
}
